﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text.huishuo
{
    //输入一个字符串，打印出该字符串中字符的所有排列。
    //例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串abc、acb、bac、bca、cab 和cba。
    public class StrType
    {
        List<String> res = new List<String>();
        char[] c;
        public String[] permutation(String s)
        {
            c = s.ToCharArray();
            dfs(0);
            return res.ToArray() ;
        }
        void dfs(int x)
        {
            if (x == c.Length - 1)
            {
                res.Add(string.Join("", c));      // 添加排列方案
                return;
            }
            HashSet<Char> set = new HashSet<Char>();
            for (int i = x; i < c.Length; i++)
            {
                if (set.Contains(c[i])) continue; // 重复，因此剪枝
                set.Add(c[i]);
                swap(i, x);                      // 交换，将 c[i] 固定在第 x 位
                dfs(x + 1);                      // 开启固定第 x + 1 位字符
                swap(i, x);                      // 恢复交换
            }
        }
        void swap(int a, int b)
        {
            char tmp = c[a];
            c[a] = c[b];
            c[b] = tmp;
        }
    }
}
